package com.lihepeng.leecode.frequency.LinkedList;

/**
 * 牛客高频之 链表指定区域反转
 *
 */
public class Solution02 {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if (head == null) {
            return null;
        }
        ListNode dumpy = new ListNode(-1);
        dumpy.next = head;
        ListNode pre = dumpy;
        for (int i=0;i<m-1;i++) {
            pre = pre.next;
        }
        ListNode right = dumpy;

        for (int i=0;i<n-m+1;i++) {
            right = right.next;
        }
        //3.截取出一个子链表
        ListNode leftNode = pre.next;
        ListNode cur = right.next;
        pre.next = null;
        right.next = null;
        revertList(leftNode);

        // 重新拼接链表
        pre.next = right;
        leftNode.next = cur;

        return dumpy.next;
    }

    /**
     * 翻转链表
     */
    private void revertList(ListNode listNode){
        if (listNode == null) {
            return;
        }
        ListNode cur = listNode;
        ListNode preNode = null;
        while (cur!=null) {
            ListNode nextNode = cur.next;
            cur.next = preNode;
            preNode = cur;
            cur = nextNode;
        }
    }
}
